#include <stdio.h>
#include <malloc.h>

/*二叉链表来表示二叉树 binary tree*/
struct Node{
    //1.数据域
    char data;
    //2.指针域
    struct  Node *left;
    struct  Node *right;
};
typedef struct Node *BTnode;
//op1.写一个创建结点并赋值的函数
BTnode createNode(char value){
    BTnode node=malloc(sizeof (BTnode));
    node->data=value;
    node->left=NULL;
    node->right=NULL;

    return node;
}
/*
 * 用递归来写中序遍历
 * */

void inOrder(BTnode root){
    if(root==NULL){
        return;
    } else{
        inOrder(root->left);
        printf("%c ",root->data);
        inOrder(root->right);
    }
}
//求树的高度
/*
 * 树的高度height=Max[左子树的高度left,右子树的高度]+1
 * 函数名：getHeight()
 * 输入：树(树的根结点)
 * 输出：树的高度 数值类型 int
 *
 * */
int getHight(BTnode root){
    if(root=NULL){
        return 0;
    }
    int hl=getHight(root->left);
    int hr=getHight(root->right);
    if(hl>hr){
        return hl+1;
    } else
        return  hr+1;

}
//求叶子结点的数量
/*
 *
 * 用递归的思想来实现求叶子结点的数量
 * f(root)=f(f.left)+f(f.right)
 * 叶子结点：node.left==node.right==NULL
 *
 * 函数名：leaf_count()
 * 输入：树（根）
 * 输出：叶子的数量 int
 * */
int leaf_count(BTnode root){
    //1.树为空
    if(root ==NULL)
        return 0;
    if(root->left=NULL&&root->right==NULL)
        return 1;
    return leaf_count(root->left)+ leaf_count(root->right);
}
void preOrder(BTnode root){
    if(root){
        //遍历过程：
        //（1）访问根节点
        printf("%c ",root->data);
        //（2）前序遍历左子树
        preOrder(root->left);
        //（3）前序遍历右子树
        preOrder(root->right);
    }
}

void postOrder(BTnode root){
    if(root){
        //遍历过程：
        //（1）后序遍历左子树
        postOrder(root->left);
        //（2）后序遍历右子树
        postOrder(root->right);
        //（3）访问根节点
        printf("%c ",root->data);
    }
}

/*
 * 层序遍历 ：借助队列来实现
 层级遍历的步骤：
（1）根结点入队
然后循环下列部分：
  （2）访问队首元素
  （3）如过该元素所在结点的左结点或右子结点不为空，则将其按左右子结点的顺序
        入队。
直达队列为空，结束该循环

 * */
void levelOrder(BTnode root)
{
    if(root==NULL)
        return;
    //1.创建队列
    //1.定义了一个数组
    BTnode *data[1000];
    int front=0;
    int rear = 0;
//2.根结点进队列
    data[rear++]=root;
    BTnode tmp;
    while(front!=rear)
    {
        //出队
        tmp=data[front++];
        //打印
        printf("%c ",tmp->data);
        //若存在左子节点，左结点进队
        if(tmp->left){
            data[rear++]=tmp->left;
        }
        //若存在右子节点，右子结点进队
        if(tmp->right){
            // EnQueue(queue,tmp->right);
            data[rear++]=tmp->right;
        }
    }
}

//动态创建二叉树   从控制台输入一串字符，根据字符创建二叉树
/*
 * 函数名：createBinTree()
 * 输入：根
 * 输出：返回二叉树（二叉树的根结点）
 * */
BTnode createBinTree(BTnode root){
    //从控制台获取输入字符
    char str;
    scanf("%c",&str);
    //  若输入的是一个“#”字符，则表明该二叉树为空树，即root=NULL;
    if(str=='#'){
        root=NULL;
    }
    else{//  否则输入的字符应该付给root->data，之后依次递归即那里它的左子树和右子树。
        root= malloc(sizeof(BTnode));
        root->data=str;
        root->left= createBinTree(root->left);
        //root->right= createNode(root->right);
        root->right= createBinTree(root->right);
    }
    return root;
}
int main() {
    //手动连接
    BTnode nodeA = createNode('A');
    BTnode nodeB = createNode('B');
    BTnode nodeD = createNode('D');
    BTnode nodeI = createNode('I');
    BTnode nodeF = createNode('F');
    BTnode nodeL = createNode('L');
    //第一层
    nodeA->left=nodeB;
    nodeA->right=nodeD;

    //第二层  B  D
    nodeB->right=nodeF;
    nodeD->left=nodeI;

    //第三层 F  I
    nodeF->left=nodeL;

   //中序、前序、后序
    inOrder(nodeA);
    printf("\n");
    preOrder(nodeA);
    printf("\n");
    postOrder(nodeA);
    printf("\n");
    //层序遍历
    levelOrder(nodeA);
    printf("\n");



    // printf("Hello, World!\n");
    return 0;
}
